\section{Linear operations on sorted ranges}

In this section, we will discuss algorithms operating on sorted ranges in linear time. The same functionality on unsorted ranges would require algorithms operating in quadratic time.

\subsection{\texorpdfstring{\cpp{std::includes}}{\texttt{std::includes}}}
\index{\cpp{std::includes}}

The \cpp{std::includes} algorithm will determine whether one range (all elements) is contained within another range.

\cppversions{\texttt{includes}}{\CC98}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{(input\_range, input\_range)}}{\texttt{(forward\_range, forward\_range)}}{\texttt{operator<}}{\texttt{strict\_weak\_ordering}}

\begin{codebox}[breakable]{\href{https://compiler-explorer.com/z/od9oa6xEP}{\ExternalLink}}
\footnotesize Example of using \cpp{std::includes} to check whether a string contains all English (lower-case) letters.
\tcblower
\cppfile{code_examples/algorithms/includes_code.h}
\end{codebox}

The example uses \cpp{std::iota} to generate the lower-case letters (line 2), which requires the destination vector to be pre-allocated (line 1).

\subsection{\texorpdfstring{\cpp{std::merge}}{\texttt{std::merge}}}
\index{\cpp{std::merge}}

The \cpp{std::merge} algorithm merges two sorted ranges, with the output written to a third range which cannot overlap with either of the input ranges.

\cppversions{\texttt{merge}}{\CC98}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{(input\_range, input\_range) -> output\_iterator}}{\texttt{(forward\_range, forward\_range) -> forward\_iterator}}{\texttt{operator<}}{\texttt{strict\_weak\_ordering}}

The merge operation is stable. Equal elements from the first range will be ordered before equal elements from the second range.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/fj3rzovKf}{\ExternalLink}}
\footnotesize Example of using \cpp{std::merge}.
\tcblower
\cppfile{code_examples/algorithms/merge_code.h}
\end{codebox}

The parallel version requires the output to be a forward range (represented by a \cpp{forward_iterator}). Therefore, we cannot use wrappers like \cpp{std::back_inserter} and must preallocate the output range to sufficient capacity.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/oEPTe7GnY}{\ExternalLink}}
\footnotesize Example of parallel \cpp{std::merge}.
\tcblower
\cppfile{code_examples/algorithms/merge_par_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::inplace_merge}}{\texttt{std::inplace\_merge}}}
\index{\cpp{std::inplace_merge}}

The \cpp{std::inplace_merge} algorithm merges two consecutive sub-ranges.

\cppversions{\texttt{inplace\_merge}}{\CC98}{N/A}{\CC17}{\CC20}
\constraints{\texttt{(bidirectional\_range, bidirectional\_iterator)}}{\texttt{(bidirectional\_range, bidirectional\_iterator)}}{\texttt{operator<}}{\texttt{strict\_weak\_ordering}}

When using the iterator-based interface, the middle iterator (i.e. the iterator to the first element of the second sub-range) is the second argument.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/8Ge81Gojr}{\ExternalLink}}
\footnotesize Example of using \cpp{std::inplace_merge}.
\tcblower
\cppfile{code_examples/algorithms/inplace_merge_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::unique}, \cpp{std::unique_copy}}{\texttt{std::unique}, \texttt{std::unique\_copy}}}
\index{\cpp{std::unique}}
\index{\cpp{std::unique_copy}}

The \cpp{std::unique} algorithm removes consecutive duplicate values. The typical use case is in conjunction with a sorted range. However, this is not a requirement of \cpp{std::unique}.

\cppversions{\texttt{unique}}{\CC98}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{forward\_range}}{\texttt{forward\_range}}{\texttt{operator==}}{\texttt{binary\_predicate}}

Because unique works in-place and cannot resize the underlying range, it leaves the end of the range with unspecified values and returns an iterator to the beginning of this sub-range.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/7bcKTfe9b}{\ExternalLink}}
\footnotesize Example of using \cpp{std::unique}.
\tcblower
\cppfile{code_examples/algorithms/unique_code.h}
\end{codebox}

The \cpp{std::unique_copy} is a variant of \cpp{std::unique} that outputs the unique values to a second range.

\cppversions{\texttt{unique\_copy}}{\CC98}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{input\_range -> output\_iterator}}{\texttt{forward\_range -> forward\_iterator}}{\texttt{operator==}}{\texttt{binary\_predicate}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/TMP7ec6P5}{\ExternalLink}}
\footnotesize Example of using \cpp{std::unique_copy}.
\tcblower
\cppfile{code_examples/algorithms/unique_copy_code.h}
\end{codebox}
